#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//void Quicksort(int* a, int begin, int end)
//{
//	if (begin >= end)
//	{
//		return;
//	}
//	/*int keyi = begin;
//	int left = begin;
//	int right = end;
//	while (left<right)
//	{
//		while (left < right && a[right] >= a[keyi])
//		{
//			--right;
//		}
//		while (left < right && a[left] <= a[keyi])
//		{
//			++left;
//		}
//		swap(&a[right], &a[left]);
//	}
//	swap(&a[keyi], &a[right]);
//	keyi = right;*/
//	int key = a[begin];
//	int hole = begin;
//	int left = begin;
//	int right = end;
//	while (left < right)
//	{
//		while (left < right && a[right] >= key)
//		{
//			--right;
//		}
//		a[hole] = a[right];
//		hole = right;
//		while (left < right && a[left] < key)
//		{
//			++left;
//		}
//		a[hole] = a[left];
//		hole = left;
//	}
//	a[left] = key;
//	hole = left;
//	Quicksort(a, begin, hole - 1);
//	Quicksort(a, hole + 1, end);
//}
void Quicksort(int* a, int* begin, int* end)
{
	if (begin >= end)
	{
		return;
	}
	int* key = begin;
	int* prev = begin;
	int* cur = begin + 1;
	while (cur <= end)
	{
		if (*key < *cur)
		{
			cur++;
		}
		else
		{
			++prev;
			swap(prev, cur);
			++cur;
		}
	}
	swap(prev, key);
	key = prev;
	Quicksort(a, begin, key - 1);
	Quicksort(a, key + 1, end);
}
int main()
{
	int b[] = { 1,5,7,8,9,6,4,2,13,3,4,4,5,9 };
	Quicksort(b, &b[0], &b[sizeof(b) / sizeof(b[0]) - 1]);
	for (int i = 0; i < sizeof(b) / sizeof(b[0]); i++)
	{
		printf("%d ", b[i]);
	}
	return 0;
}
